//二叉搜索树
public class BinarySearchTree {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root;

    public void Insert(int key) {
        //比关键字大的值放到右边
        //比关键字小的值放到左边

        TreeNode parent = null;
        if (root == null)
            root = new TreeNode(key);
        else {
            TreeNode cur = root;
            while (cur != null) {
                if (key > cur.val) {
                    parent = cur;
                    cur = cur.right;
                } else {
                    parent = cur;
                    cur = cur.left;
                }//cur结点更新之前，用parent来保存cur的上一个结点
            }

            if (key < parent.val) {
                parent.left = new TreeNode(key);
            } else parent.right = new TreeNode(key);
        }
    }

    public boolean Search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (val > cur.val) {
                cur = cur.right;
            } else if (val < cur.val) {
                cur = cur.left;
            } else return true;
        }
        return false;
    }

    public boolean Modify(int val, int new_val) {
        //先找到要修改的值
        TreeNode cur = root;
        while (cur != null) {
            if (val > cur.val) {
                cur = cur.right;
            } else if (val < cur.val) {
                cur = cur.left;
            } else {
                cur.val = new_val;
                return true;
            }
        }
        return false;
    }

    public void delete(int key) {
        TreeNode cur = root;
        TreeNode parent = null;


        while (cur != null) {
            if (key > cur.val) {
                parent = cur;
                cur = cur.right;
            } else if (key < cur.val) {
                parent = cur;
                cur = cur.left;
            } else {
                removeNode(cur, parent);
                return;
            }
        }
        System.out.println("没有你要删除的");
    }

    public void removeNode(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {   //目标节点左边为空
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else parent.right = cur.right;
        } else if (cur.right == null) {   //目标节点右边为空
            if (root == null) {
                root = cur.left;
            } else if (cur == parent.right) {
                parent.right = cur.left;
            } else parent.left = cur.left;
        } else {
            //都不为空
            TreeNode targetParent = cur;
            TreeNode target = cur.right;

            //搜索到关键字节点cur，然后我们应该保证key之后的位置应满足二叉搜索树的条件，
            //找到合适的数据(和cur交换之后能满足二叉搜索树条件)之后直接替换cur的值，然后删除那个合适的节点就行了

            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;

            if(targetParent.left == target)
                targetParent.left = target.right;
            else targetParent.right = target.right;

        }
    }
}
